﻿using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;

namespace ns
{

    public class OfferSolution : MonoBehaviour
    {
        //剑指 Offer 29. 顺时针打印矩阵
        //https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
        //解法：https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/solution/mian-shi-ti-29-shun-shi-zhen-da-yin-ju-zhen-she-di/
        //算法：模拟边界，t,b,l,r 边界收缩+1和-1 ，判断是否打印成功
        //栗子：123 456 789   123 698 745
        public int[] SpiralOrder(int[][] matrix)
        {
            if (matrix.Length == 0) return new int[0];
            int l = 0, r = matrix[0].Length - 1, t = 0, b = matrix.Length - 1, x = 0;   //l=0 , r=2 ,t=0 , b=2;
            int[] res = new int[(r + 1) * (b + 1)];
            while (true)
            {
                for (int i = l; i <= r; i++) //从左向右
                {
                    res[x] = matrix[t][i];  //[0,0] [0,1] [0,2] t=0 
                    x++;
                }
                t++;   //t=1 
                if (t > b) break;

                for (int i = t; i <= b; i++) //从上往下
                {
                    res[x] = matrix[i][r]; // [1,2] [2,2]
                    x++;
                }
                r--;  //r=1
                if (l > r) break;

                for (int i = r; i >= l; i--) //从右往左
                {
                    res[x] = matrix[b][i];  // [2,1] [2,0]
                    x++;
                }
                b--; //b=1
                if (t > b) break;

                for (int i = b; i >= t; i--) //从下往上
                {
                    res[x] = matrix[i][l]; // [0,1]
                    x++;
                }
                l++;
                if (l > r) break;
            }
            return res;
        }




        //剑指 Offer 52. 两个链表的第一个公共节点
        //https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
        //算法1：指针相遇
        //算法2：hashset
        public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
        {
            ListNode nodeA = headA;
            ListNode nodeB = headB;

            while (nodeA != nodeB)
            {
                nodeA = nodeA != null ? nodeA.next : headB;
                nodeB = nodeB != null ? nodeB.next : headA;
            }
            return nodeA;
        }

        //剑指 Offer 03. 数组中重复的数字
        //https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
        //算法1：hashset
        public int FindRepeatNumber(int[] nums)
        {
            HashSet<int> hash = new HashSet<int>();
            for (int i = 0; i < nums.Length; i++)
            {
                if (hash.Contains(nums[i]))
                {
                    return nums[i];
                }
                hash.Add(nums[i]);
            }
            return 0;
        }

        //剑指 Offer 09. 用两个栈实现队列
        //https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
        //算法：2个栈的特性~动态规划
        public class CQueue
        {
            Stack s1; //入栈
            Stack s2; //出栈
            //Stack<int> s1; //入栈
            //Stack<int> s2; //出栈

            public CQueue()
            {
                s1 = new Stack();
                s2 = new Stack();
            }

            public void AppendTail(int value)
            {
                if (s1.Count==0)
                {

                }
                s1.Push(value); //s1就是入栈
            }

            public int DeleteHead()
            {
                if (s2.Count==0)
                {
                    while (s1.Count!=0)
                    {
                        s2.Push(s1.Pop());
                    }
                }
                if (s2.Count==0)
                {
                    return -1;
                }
                return (int)s2.Pop();
            }
        }



        public class ListNode
        {
            public int val;
            public ListNode next;
            public ListNode(int x)
            {
                val = x;
                next = null;
            }
        }
    }
}